package leecode;

import sun.reflect.generics.tree.Tree;

import java.util.*;

public class LeetCode20 {
    public double myPow(double x, int n) {
        double sum=1;
        if(n<0){
            x=1/x;
            n=-n;
        }
        if(x==-1){
            if(n%2==0){
                return 1;
            }else{
                return -1;
            }
        }
        if(n==0||x==1){
            return 1;
        }
        if(n<=Integer.MIN_VALUE){
            return 0;
        }
        for (int i = 0; i < n; i++) {
            sum*=x;
        }
        return sum;
    }
    //已知前序和中序遍历，求后续
    private Map <Integer,Integer>map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n=preorder.length;
        if(n==0){
            return null;
        }
        map=new HashMap<Integer,Integer>();
        for (int i = 0; i < n; i++) {
            map.put(inorder[i],i);
        }
        return buildTree(preorder,inorder,0,n-1,0,n-1);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if(preorder_left>preorder_right||inorder_left>inorder_right){
            return null;
        }
        //前序遍历第一个节点就是根节点
        int roots=preorder[preorder_left];
        TreeNode root=new TreeNode(roots);
        //中序遍历中根的位置
        int site=map.get(roots);
        //左子树的节点数目
        int left_size=site-inorder_left;
        root.left=buildTree(preorder,inorder,preorder_left+1,left_size+preorder_left,inorder_left,site-1);
        root.right=buildTree(preorder,inorder,left_size+preorder_left+1,preorder_right,site+1,inorder_right);
        return root;
    }

    public static void main(String[] args) {
        int[]arr={1,2,3};
        int[]arr2={2,3,1};
        LeetCode20 leetCode20=new LeetCode20();
        leetCode20.buildTree(arr,arr2);

    }
    //判断是不是后续遍历，单调栈做法
    public boolean verifyPostorder(int[] postorder) {
        Stack<Integer>stack=new Stack<>();
        int max=Integer.MAX_VALUE;
        for (int i = postorder.length-1; i >=0 ; i--) {
            if(postorder[i]>max){
                return false;
            }
            while (!stack.empty()&&postorder[i]<stack.peek()){
                max=stack.pop();
            }
            stack.push(postorder[i]);
        }
    return true;
    }
    //做法2，递归性质判断
    public boolean verifyPostorder2(int[] postorder) {
        return judge(postorder,0,postorder.length-1);
    }

    private boolean judge(int[] postorder, int i, int j) {
        if(i>=j){//终止条件，如果剩一个元素就为true
            return true;
        }
        int p=i;
        while (postorder[p]<postorder[j]){//找出第一个根节点，左边为左树，右边为右树
            p++;
        }
        int m=p;//记录根节点
        while (postorder[p]>postorder[j]){//一般右树都会比根节点大，如果小的话，p！=j，下面的判断就会返回false
            p++;
        }
        return i==j&&judge(postorder,i,m-1)&&judge(postorder,m+1,j);
    }

}
